package com.clps.algorithm.chapter14.环形房屋偷盗;

/**
 *一个环形街道上有若干房屋。输入一个数组表示该街上的房屋内财产的数量。如果这条街道上相邻的两家被盗就会自动触发报警系统。一个小偷打算到给街去偷窃，请计算该小偷最多能偷到多少财产。
 * 例如，街道上五家的财产用数组[2, 3, 4, 5, 3]表示，如果小偷到下标为1和3的房屋内偷窃，那么他能偷取到价值8的财物，
 * 这是他在不触发报警系统情况下能偷取到的最多的财物，如图14.4所示。
 */
public class 环形房屋偷盗_01 {

    public static void main(String[] args) {

    }

    public  int rob(int[] nums){
        if(nums.length ==0){
            return  0;
        }

        if(nums.length ==1){
            return nums[0];
        }

        int result1 = helper(nums,0,nums.length -1);
        int result2 = helper(nums,1,nums.length-2);
        return  Math.max(result1,result2);
    }

    private int helper(int[] nums, int start, int end) {
        int[] dp = new int[2];
        dp[0] = nums[start];

        if(start< end){
            dp[1] = Math.max(nums[start],nums[start+1]);
        }

        for (int i = start+2; i <=end ; i++) {
            int j = i-start;
            dp[j%2] = Math.max(dp[(j-1) % 2], dp[(j-2) % 2] + nums[i]);
        }

        return  dp[(end-start) % 2];
    }
}
